import {BSTree,BSTNode} from './BSTree'

export class AVLNode extends BSTNode {

    updateDepth() {
        let left=this.left && this.left.depth || 0;
        let right=this.right && this.right.depth ||0;
        this.depth=Math.max(left,right)+1;
        this.balance=left-right;
    }

    leftRotate(){
        this.right.rotate();
        this.updateDepth();
    }

    rightRotate(){
        this.left.rotate();
        this.updateDepth();
    }

    fix() {
        this.updateDepth();
        if (this.balance <= -2) {
            if (this.right.balance>=1){
                this.right.rightRotate();
            }
            this.leftRotate();
        } else if (this.balance >= 2) {
            if (this.left.balance<=-1){
                this.left.leftRotate();
            }
            this.rightRotate();
        }
        //console.log("fix",this.value);
    }
}

export class AVLTree extends BSTree{

    nodeType(){
        return AVLNode;
    }
    insert(value){
        let node=super.insert(value);
        let i=0;
        for (let p=node;p!==this;p=p.parent){
            if (++i>30) break;
            p.fix();
        }
        return node;
    }

    remove(){
        throw Error("not implement")
    }
}